package eol.vm;

import java.io.PrintStream;
import java.util.*;


import eol.compiler.CompileTimeError;
import eol.vm.Value.*;
import util.Assert ;

/** The virtual machine for EOL. 
 * <p>The state of the machine at compile time is represented by</p>
 * <ul><li>The codeStore: an array of code segments. 
 *         Each segment holds the code for one function or a top level item.
 *     <li>An array of constant values.
 * </ul>
 * At run time there is in addition:
 * <ul>
 *     <li>A function invocation consisting of:
 *         <ul><li>An environment. Each environment maps 1 or more
 *               variable names to values.
 *             <li>A segment number, indexing the code store.
 *             <li>The program counter.</li></ul>
 *     <li>A stack of values.
 *     <li>An stack of function invocations, used by the CALL and RETURN instructions
 * </ul>
 */
public class Machine implements InstructionSet {
    
	
    
    /** An invocation is an unfinished execution of a function */
    private static class Invocation {
        int pc ;
        int segNum ;
        Environment env ;
    }
    
    /** The state of the machine */
    private static class MachineState {	
    		/** The index of the segment currently being executed (if any)*/
        int segNum ;
        
        /** The address of the next instruction to be executed. */
        int pc ;
        
        /** The environment that the code is being executed in. */
        Environment env ;
        
        /** The stack of values */
        Stack<Value> stack = new Stack<Value>() ;
        
        /** A stack of incomplete invocations.
         * This stack is pushed on a CALL and popped on a RETURN */
        Stack<Invocation> invocationStack = new Stack<Invocation>() ;
    }
    
    private static final int CONST_SIZE = 256*256;
    private CodeStore codeStore = new CodeStore() ;
    private Value[] constantsTable = new Value[CONST_SIZE];
    { constantsTable[0] = NilValue.theNil ; }
    { constantsTable[1] = new StringValue("true") ; }
    private int constantCount = 2 ;
    private StringValue theTrue = (StringValue) constantsTable[1] ;
    
    private Environment globalEnvironment = new Environment(
    		new ArrayList<Value.StringValue>(),
    		new ArrayList<Value>(),
    		null) ;
    
    public boolean verbose = true ;
    public boolean tracing = true ;
    private PrintStream out = System.out ;
    private PrintStream err = System.out ;

     /** Add a string to the constants table.
     * Each string is associated with a unique int which can be used as
     * an operand of the CONST, FETCH, STORE, or NEW_VAR instructions. */
    public int interString(String s) throws CompileTimeError {
        int i ;
        for( i = 0 ; i < constantCount ; ++i ) {
            if( constantsTable[i].getType() == Type.STRING && ((StringValue)constantsTable[i]).val.equals(s) ) {
                break ; }
        }
        if( i == constantCount ) {
            if( constantCount == CONST_SIZE )
                throw new CompileTimeError("Too many constants") ;
            constantsTable[constantCount++] = new StringValue(s) ; }
        if( verbose ) { err.println( "Constant #"+ i +" is "+ constantsTable[i] ) ; }
        return i;
    }
    
    /** Add a number to the constants table.
     * Each number is associated with a unique int which can be used as
     * an operand of the CONST instruction. */
    public int interDouble(double d) throws CompileTimeError {
        int i ;
        for( i = 0 ; i < constantCount ; ++i ) {
            if( constantsTable[i].getType() == Type.DOUBLE && ((DoubleValue)constantsTable[i]).val == d ) 
                break ;
        }
        if( i == constantCount ) {
            if( constantCount == CONST_SIZE )
                throw new CompileTimeError("Too many constants") ;
            constantsTable[constantCount++] = new DoubleValue(d);  }
        if( verbose ) { err.println( "Constant #"+ i +" is "+ constantsTable[i] ) ; }
        return i;
    }
    
    public int startSegment() {
    		return codeStore.startSegment() ;
    }
    
    public void endSegment() {
    		codeStore.endSegment() ;
    }

    /** Add one instruction to end of the current segment. */
    public void emit(byte opCode) {
    		int segNum = codeStore.getCurrentSegNum() ;
    		int addr = codeStore.getCurrentCodeAddr() ;
        switch (opCode) {
        case RETURN:
        case START_ENV:
        case END_ENV:
        case POP :
        case ADD:
        case SUBTRACT:
        case MULTIPLY:
        case DIVIDE:
        case EQUAL:
        case NULL:
        case ATOMIC:
        case CONS:
        case HEAD:
        case TAIL:
        case PRINT:
            codeStore.put(addr, opCode);
            if( verbose ) printInstruction(segNum, addr) ;
            break ;
        default:
            Assert.notReached("Wrong number of operand(s)");
        }
    }

    /** Add one instruction to end of the current segment. */
    public void emit(byte opCode, int operand, int operandLength) {
        // Currently all operands are 3 bytes long.
        if( operandLength != 3 ) {
        		Assert.notReached("Wrong number of operand(s)");
        }
        switch (opCode) {
        case FETCH:
        case STORE:
        case NEW_VAR:
        case CONST:
        case BRANCH:
        case BRANCH_ON_NIL:
        case CALL :
        case MAKE_CLOSURE :
        	    int segNum = codeStore.getCurrentSegNum() ;
        		int addr = codeStore.getCurrentCodeAddr() ;
        
            codeStore.put(addr, opCode) ;
            putOperand(operand, addr+1);
            if( verbose ) printInstruction(segNum, addr) ;
            return;
        default:
            throw new AssertionError("Wrong operand(s)");
        }
    }
    
    public int getCurrentCodeAddr( ) {
    		return codeStore.getCurrentCodeAddr() ; 
    }
    
    /** Change the destination of a branch instruction. */
    public void backPatch( int branchLocation, int operand) {
    		int segNum = codeStore.getCurrentSegNum() ;
    		putOperand(operand, branchLocation+1);
        if( verbose ) {
            err.println("Backpatched ") ;
            if( verbose ) printInstruction(segNum, branchLocation) ;; }
    }

    /** Run the program. */
    public void execute(int segNum ) throws ExecutionError {
        if( tracing ) err.println("Execution Begins") ;
        
        MachineState state = new MachineState() ;
        state.pc = 0 ;
        state.segNum = segNum ;
        state.env = globalEnvironment ;
        
        instructionLoop: while(true) {
            if( tracing ) {
                printStack(state.stack) ;
                state.env.print( err ) ;
                printInstruction( state.segNum, state.pc) ;
            }
            byte opCode = codeStore.fetch( state.segNum, state.pc++ ) ;
            switch( opCode ) {
            case CALL : {
                byte c = codeStore.fetch(state.segNum, state.pc++) ;
                byte b = codeStore.fetch(state.segNum, state.pc++) ;
                byte a = codeStore.fetch(state.segNum, state.pc++) ;
                int count = bytesToInt(c, b, a) ;
	            	List<Value> args = new LinkedList<Value>() ;
	            	for( int i = 0 ; i < count ; i++ ) {
	            		args.add(0, pop( state.stack ) ) ; }
	            	Value closureValue = pop( state.stack ) ;
	            	check( closureValue.getType() == Type.CLOSURE,
	            			"Expected a function value in CALL" ) ;
	            	Closure closure = closureValue.asClosure() ;
	            	check( args.size() == closure.params.size(),
	            			"Function has " +closure.params.size()+
	            			" parameters. But there were " +args.size()+ " arguments." ) ; 
	            	// All checks passed. We can get to work.
	            	// Push the current invocation
	            	Invocation invocation = new Invocation() ;
	            	invocation.pc = state.pc ;
	            	invocation.segNum = state.segNum ;
	            	invocation.env = state.env ;
	            	state.invocationStack.push( invocation ) ;
	            	// Set the current invocation
	            	state.env = new Environment(closure.params, args, closure.env) ;
	            	state.segNum = closure.segNum ;
	            	state.pc = 0 ;
            } break ;
            case RETURN: {
                if( state.invocationStack.isEmpty() )
                		break instructionLoop ;
                else {
                    Invocation top = state.invocationStack.pop() ; 
                    state.segNum = top.segNum ;
                    state.pc = top.pc ;
                    state.env = top.env ; }
            } break ;
            case START_ENV: {
            		state.env = new Environment(
            							new ArrayList<StringValue>(),
            							new ArrayList<Value>(),
            							state.env) ;
            } break ;
            case END_ENV: {
            		state.env = state.env.next ;
            } break ;
            case POP: {
            		pop( state.stack ) ;
            } break ;
            case ADD: case SUBTRACT: case MULTIPLY: case DIVIDE: {
                double y = pop(state.stack).asDouble() ;
                double x = pop(state.stack).asDouble() ;
                double z ;
                switch( opCode ) {
                case ADD: z = x+y ; break ;
                case SUBTRACT: z = x-y ; break ;
                case MULTIPLY: z = x*y ; break ;
                case DIVIDE: z = x/y ; break ;
                default: Assert.notReached() ; z = 0; }
                if( z==Double.NaN || z==Double.POSITIVE_INFINITY || z==Double.NEGATIVE_INFINITY )
                		throw new ExecutionError("Arithmetic error.") ;
                state.stack.push( new DoubleValue(z) ) ; }
            break ;
            case EQUAL: {
                Value y = pop(state.stack) ;
                Value x = pop(state.stack) ;
                push( state.stack, x.isEqualTo( y ) ) ;
            } break ;
            case CONS:{
                Value y = pop(state.stack) ;
                Value x = pop(state.stack) ;
                state.stack.push( new ConsValue( x, y ) ) ;
            } break ;
            case NULL: {
                push( state.stack, pop(state.stack).getType() == Type.NIL ) ;
            } break ;
            case ATOMIC: {
                push( state.stack, pop(state.stack).getType() != Type.CONS ) ;
            } break ;
            case HEAD: {
            		state.stack.push( pop(state.stack).asConsValue().head ) ;
            } break ;
            case TAIL: {
            		state.stack.push( pop(state.stack).asConsValue().tail ) ;
            } break ;
            case PRINT: {
                out.println( pop(state.stack).toString() ) ;
            } break ;
            
            // The following instructions all have a 3 byte integer operand.
            case FETCH:
            case STORE:
            case NEW_VAR:
            case MAKE_CLOSURE:
            case CONST:
            case BRANCH:
            case BRANCH_ON_NIL: {
                byte c = codeStore.fetch(state.segNum, state.pc++) ;
                byte b = codeStore.fetch(state.segNum, state.pc++) ;
                byte a = codeStore.fetch(state.segNum, state.pc++) ;
                int operand = bytesToInt(c, b, a) ;
                switch( opCode ) {
                case FETCH: {
                    StringValue var = constantsTable[ operand ].asStringValue() ;
                    state.stack.push( state.env.get( var ) ) ;
                } break ;
                case STORE: {
                		StringValue var = constantsTable[ operand ].asStringValue() ;
                    Value x = top(state.stack) ;
                    state.env.set(var, x) ;
                } break ;
                case NEW_VAR: {
                		StringValue var = constantsTable[ operand ].asStringValue() ;
                    Value x = top(state.stack) ;
                    state.env.newVar(var, x) ;
                } break ;
                case CONST:  {
                		state.stack.push( constantsTable[ operand ] ) ;
                } break ;
                case BRANCH: {
                    check( 0 <= operand && operand < codeStore.segmentSize( state.segNum ),
                    		 "Branch destination is out of bounds" ) ;
                    state.pc = operand ; 
                } break ;
                case BRANCH_ON_NIL: {
                    check( 0 <= operand && operand < codeStore.segmentSize( state.segNum ),
                    		"Branch destination is out of bounds" ) ;
                    if( pop(state.stack).isEqualTo(NilValue.theNil) ) state.pc = operand ; 
                } break ;
                case MAKE_CLOSURE: {
	                	check( 0 <= operand && operand < codeStore.size(),
	                			"MAKE_CLOSURE operand refers to a non existant segment" ) ;
	            		Value countVal = pop( state.stack ) ;
	            		check( countVal.getType() == Type.DOUBLE, "Expected parameter count in MAKE_CLOSURE." ) ;
	            		int count = (int) countVal.asDouble() ;
	            		List<StringValue> params = new LinkedList<StringValue>() ;
	            		for( int i = 0 ; i < count ; i++ ) {
	            			Value param = pop( state.stack ).asStringValue() ; ;
	            			check( param.getType() == Type.STRING, "Expeced parameter to be a string in MAKE_CLOSURE." ) ;
	            			params.add(0, param.asStringValue() ) ; }
	            		Closure closure = new Closure(params,state.env, operand ) ;
	            		state.stack.push( closure ) ;
                } }
            } break ;
            default: throw new ExecutionError("bad opcode "+opCode+" at " + (state.pc-1) ) ;
            }
        }
        // If we finish with no error, we add any declarations to
        // the global environment
        globalEnvironment = state.env ;
    }
    
    private void printStack( List<Value> stack ) {
        err.print("stack is: ") ;
        if( stack.size() == 0 ) err.println("empty") ;
        else {
            int k = Math.min( 5, stack.size() ) ;
            for( int i=0 ; i<k ; ++i ) 
                err.print( stack.get(stack.size()-1-i) + "  ") ;
            err.println(); 
        }
    }
    
    private void printInstruction( int segNum, int locn ) {
            err.println( segNum+ ":" +locn+ ": " + formatInstruction( segNum, locn ) ) ;
    }
    
    private String formatInstruction(int segNum, int locn)  {
        CodeStore.Segment segment = codeStore.segments.get( segNum ) ;
        byte opCode = segment.fetch(locn++) ;
        switch( opCode ) {
        case RETURN: return "RETURN" ;
        case START_ENV: return "START_ENV" ;
        case END_ENV: return "END_ENV" ;
        case POP: return "POP" ;
        case ADD: return "ADD" ;
        case SUBTRACT: return "SUBTRACT" ;
        case MULTIPLY: return "MULTIPLY" ;
        case DIVIDE: return "DIVIDE" ;
        case EQUAL: return "EQUAL" ;
        case CONS: return "CONS" ;
        case NULL: return "NULL" ;
        case ATOMIC: return "ATOMIC" ;
        case HEAD: return "HEAD" ;
        case TAIL: return "TAIL" ;
        case PRINT: return "PRINT" ;
        
        case CALL: 
        case FETCH:
        case STORE:
        case NEW_VAR:
        case CONST:
        case BRANCH:
        case BRANCH_ON_NIL:
        case MAKE_CLOSURE: {
            byte c = segment.fetch(locn++) ;
            byte b = segment.fetch(locn++) ;
            byte a = segment.fetch(locn++) ;
            int operand = bytesToInt(c, b, a) ;
            switch( opCode ) {
            case CALL: return "CALL "+operand ; 
            case BRANCH: return "BRANCH "+operand ;
            case BRANCH_ON_NIL: return "BRANCH_ON_NIL "+operand ;
            case MAKE_CLOSURE: return "MAKE_CLOSURE "+operand ;
            case FETCH: case STORE: case NEW_VAR: case CONST:
            		String operandString ;
            		if( 0 <= operand && operand <= constantCount && constantsTable[operand]!=null )
            			operandString = " (" +constantsTable[operand]+ ")" ;
            		else operandString = " ( no such constant ) " ;
            		switch( opCode ) {
            		case FETCH: return "FETCH " +operand+operandString ;
            		case STORE: return "STORE " +operand+operandString ;
            		case NEW_VAR: return "NEW_VAR " +operand+operandString ;
            		case CONST: return "CONST "+operand+operandString ;
            	}
            default: Assert.notReached() ;
            }
        } 
        default: return "Unknown opcode "+opCode ;
        }
    }
    
    int bytesToInt( byte c, byte b, byte a ) {
        // In case c is negative, the whole works needs to be negative.
        // So we put the three bytes in positions 24-31, 16-23, and 8-15.
        // And then shift right 8 bits with sign extension.
        return ((c<<24) & 0xFF000000 | (b<<16) & 0xFF0000 | (a<<8) & 0xFF00) >>> 8 ;   
    }

    private void putOperand(int operand, int addr) {
        byte a = (byte)( (operand) & 0xFF)  ;
        byte b = (byte)( (operand >> 8) & 0xFF)  ;
        byte c = (byte)( (operand >> 16) & 0xFF)  ;
        codeStore.put(addr++, c) ;
        codeStore.put(addr++, b) ;
        codeStore.put(addr, a) ;
    }

    
    void check(boolean b, String message) throws ExecutionError {
        if( !b ) throw new ExecutionError( message ) ;
    }
    
    /** pop a stack */
    <T> T pop(Stack<T> stack) throws ExecutionError {
        if( stack.isEmpty() ) throw new ExecutionError("Stack underflow") ;
        return stack.pop() ;
    }
    
    /** top of a stack */
    <T> T top(Stack<T> stack) throws ExecutionError {
        if( stack.isEmpty() ) throw new ExecutionError("Stack underflow") ;
        return stack.peek() ;
    }
    
    /* Push a boolean onto the value stack. */
    void push( Stack<Value> stack, boolean b ) {
        Value value = b ? theTrue : NilValue.theNil ; 
        stack.push( value ) ;
    }

    public void swapOutputStream(PrintStream printStream) {
        out  = printStream ;
        
    }

    public void setErrorStream(PrintStream printStream) {
        err  = printStream ;
        
    }
    
    public static class ExecutionError extends Exception {
        public ExecutionError(String mess) { super("Virtual Machine Error: "+mess) ; }
    }
}
